
# 79. 单词搜索

def exist(board, word):

    result = []
    temp = []
    def trackback(m, n, k):
        if len(temp) == len(word):
            if temp not in result:
                result.append(temp[:])
            return
        for i in range(m, len(board)):
            for j in range(n, len(board)):
                if board[i][j] == word[k]:
                    temp.append(board[m][n])
                    if i > 0 and k < len(word) - 1:
                        if board[i - 1][j] == word[k + 1]:
                            trackback(i - 1, j, k + 1)
                    if i < len(board) - 1 and k < len(word) - 1:
                        if board[i + 1][j] == word[k + 1]:
                            trackback(i + 1, j, k + 1)
                    if j > 0 and k < len(word) - 1:
                        if board[i][j - 1] == word[k + 1]:
                            trackback(i, j - 1, k + 1)
                    if i < len(board[0]) - 1 and k < len(word) - 1:
                        if board[i][j + 1] == word[k + 1]:
                            trackback(i, j + 1, k + 1)
                    temp.pop()

    trackback(0, 0, 0)
    print(result)
    return list(word) in result

if __name__ == "__main__":
    board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
    word = "ABCCED"
    exist(board,word)